package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode-cn.com
 * 
 * (done)973. 最接近原点的 K 个点
 * (done)292. Nim游戏
 * (done)500. 键盘行
 * (done)509. 斐波那契数
 * (done)867. 转置矩阵
 * (done)908. 最小差值 I
 * @author: jie.deng
 * @time: 2019年1月23日 上午9:52:41
 */
public class MySolution0123 {
	
	/**
	 * 973. 最接近原点的 K 个点
	 * 
     * 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
     * 
     * （这里，平面上两点之间的距离是欧几里德距离。）
     * 
     * 你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：points = [[1,3],[-2,2]], K = 1
     * 输出：[[-2,2]]
     * 解释： 
     * (1, 3) 和原点之间的距离为 sqrt(10)，
     * (-2, 2) 和原点之间的距离为 sqrt(8)，
     * 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
     * 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
     * 示例 2：
     * 
     * 输入：points = [[3,3],[5,-1],[-2,4]], K = 2
     * 输出：[[3,3],[-2,4]]
     * （答案 [[-2,4],[3,3]] 也会被接受。）
     *  
     * 
     * 提示：
     * 
     * 1 <= K <= points.length <= 10000
     * -10000 < points[i][0] < 10000
     * -10000 < points[i][1] < 10000
	 * @param points
	 * @param K
	 * @return
	 */
	public int[][] kClosest(int[][] points, int K) {
		int len = points.length;
		if (K >= len) {
			return points;
		}

		int[] z = new int[len];
		for (int i = 0; i < len; i++) {
			int[] point = points[i];
			z[i] = point[0] * point[0] + point[1] * point[1];
		}

		int[] sortZ = Arrays.copyOf(z, len);
		for (int i = 0; i < K; i++) {
			int minIdx = i;
			for (int j = i + 1; j < len; j++) {
				if (sortZ[j] < sortZ[minIdx]) {
					minIdx = j;
				}
			}
			if (minIdx != i) {
				sortZ[i] = sortZ[i] ^ sortZ[minIdx];
				sortZ[minIdx] = sortZ[i] ^ sortZ[minIdx];
				sortZ[i] = sortZ[i] ^ sortZ[minIdx];
			}
		}
		int[][] ret = new int[K][2];
		int idx = 0;
		for (int i = 0; i < len; i++) {
			if (idx < K && z[i] <= sortZ[K - 1]) {
				ret[idx][0] = points[i][0];
				ret[idx][1] = points[i][1];
				idx++;
			}
		}

		return ret;
	}
    
    /**
     * 292. Nim游戏
     * 
     * 你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
     * 
     * 你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
     * 
     * 示例:
     * 
     * 输入: 4
     * 输出: false 
     * 解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     *      因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
     * @param n
     * @return
     */
	public boolean canWinNim(int n) {
		return n % 4 != 0;
	}
    
    /**
     * 500. 键盘行
     * 
     * 给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
     * 
     * 示例：
     * 
     * 输入: ["Hello", "Alaska", "Dad", "Peace"]
     * 输出: ["Alaska", "Dad"]
     *  
     * 
     * 注意：
     * 
     * 你可以重复使用键盘上同一字符。
     * 你可以假设输入的字符串将只包含字母。
     * @param words
     * @return
     */
    public String[] findWords(String[] words) {
    	List<String> ret = new ArrayList<String>();
		String[] keys = { "qwertyuiop", "asdfghjkl", "zxcvbnm" };
		for (String word : words) {
			char[] arr = word.toCharArray();
			boolean flag = true;
			for (char ch : arr) {
				if (ch >= 'A' && ch <= 'Z') {
					ch = (char) (ch + 'a' - 'A');
				}
				if (keys[0].indexOf(ch) == -1) {
					flag = false;
					break;
				}
			}
			if (flag) {
				ret.add(word);
				continue;
			}

			flag = true;
			for (char ch : arr) {
				if (ch >= 'A' && ch <= 'Z') {
					ch = (char) (ch + 'a' - 'A');
				}
				if (keys[1].indexOf(ch) == -1) {
					flag = false;
					break;
				}
			}
			if (flag) {
				ret.add(word);
				continue;
			}

			flag = true;
			for (char ch : arr) {
				if (ch >= 'A' && ch <= 'Z') {
					ch = (char) (ch + 'a' - 'A');
				}
				if (keys[2].indexOf(ch) == -1) {
					flag = false;
					break;
				}
			}
			if (flag) {
				ret.add(word);
				continue;
			}
		}
		return ret.toArray(new String[ret.size()]);
    }
    
    /**
     * 509. 斐波那契数
     * 
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     * 
     * F(0) = 0,   F(1) = 1
     * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     * 给定 N，计算 F(N)。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：2
     * 输出：1
     * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
     * 示例 2：
     * 
     * 输入：3
     * 输出：2
     * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
     * 示例 3：
     * 
     * 输入：4
     * 输出：3
     * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
     *  
     * 
     * 提示：
     * 
     * 0 ≤ N ≤ 30
     * @param N
     * @return
     */
    public int fib(int N) {
		if (N == 0 || N == 1) {
			return N;
		}
		int n0 = 0, n1 = 1, i = 2;
		while (i < N) {
			int tmp = n0 + n1;
			n0 = n1;
			n1 = tmp;
			i++;
		}
		return n0 + n1;
    }
    public int fib_(int N) {
		if (N == 0 || N == 1) {
			return N;
		}
		return fib(N - 2) + fib(N - 1);
    }
    
    /**
     * 867. 转置矩阵
     * 
     *　给定一个矩阵 A， 返回 A 的转置矩阵。
     *　
     *　矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
     *　
     *　 
     *　
     *　示例 1：
     *　
     *　输入：[[1,2,3],[4,5,6],[7,8,9]]
     *　输出：[[1,4,7],[2,5,8],[3,6,9]]
     *　示例 2：
     *　
     *　输入：[[1,2,3],[4,5,6]]
     *　输出：[[1,4],[2,5],[3,6]]
     *　 
     *　
     *　提示：
     *　
     *　1 <= A.length <= 1000
     *　1 <= A[0].length <= 1000
     * @param A
     * @return
     */
    public int[][] transpose(int[][] A) {
		int lenR = A.length;
		int lenC = A[0].length;

		int[][] b = new int[lenC][lenR];
		for (int i = 0; i < lenR; i++) {
			for (int j = 0; j < lenC; j++) {
				b[j][i] = A[i][j];
			}
		}
		return b;
    }
    
    /**
     * 908. 最小差值 I
     * 
     * 给定一个整数数组 A，对于每个整数 A[i]，我们可以选择任意 x 满足 -K <= x <= K，并将 x 加到 A[i] 中。
     * 
     * 在此过程之后，我们得到一些数组 B。
     * 
     * 返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：A = [1], K = 0
     * 输出：0
     * 解释：B = [1]
     * 示例 2：
     * 
     * 输入：A = [0,10], K = 2
     * 输出：6
     * 解释：B = [2,8]
     * 示例 3：
     * 
     * 输入：A = [1,3,6], K = 3
     * 输出：0
     * 解释：B = [3,3,3] 或 B = [4,4,4]
     *  
     * 
     * 提示：
     * 
     * 1 <= A.length <= 10000
     * 0 <= A[i] <= 10000
     * 0 <= K <= 10000
     * @param A
     * @param K
     * @return
     */
    public int smallestRangeI(int[] A, int K) {
		int min = A[0];
		int max = A[0];
		for (int i = 1; i < A.length; i++) {
			if (A[i] < min) {
				min = A[i];
			} else if (A[i] > max) {
				max = A[i];
			}
		}
		return Math.max(0, max - min - 2 * Math.abs(K));
    }
}
